#include <iostream>
#include <vector>
#include <string>
#include <memory>
#include <iterator>
#include <algorithm>
using namespace std;

template <class T, class Sequence>
class queue {
    friend bool operator==(const queue& x, const queue& y);
    friend bool operator<(const queue& x, const queue& y);

public:
    typedef typename Sequence::value_type value_type;
    typedef typename Sequence::size_type size_type;
    typedef typename Sequence::reference reference;
    typedef typename Sequence::const_reference const_reference;

protected:
    Sequence c;

public:
    bool empty() const {return c.empty();}//判断队列是否为空
    size_type size() const {return c.size();}//判断队列的大小
    reference front() {return c.front();}//返回队列的第一个元素
    const_reference front() const {return c.front();}
    reference end() {return c.end();}//返回队列的最后一个元素
    const_reference end() const {return c.end();}
    void push(const value_type& x) {c.push_back(x);}//在队列中插入一个元素
    void pop() {c.pop_front();}
};

template <class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
    return x.c == y.c;
}

template <class T, class Sequence>
bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
    return x.c < y.c;
}

//
//使用vector作为默认的集合，原因是通过堆管理，希望可以通过下标快速访问每一个下标的元素
//因为优先队列以二叉树数组的方式存储
//

template <class T, class Sequence, class Compare>
class priority_queue {
public:
    typedef typename Sequence::value_type value_type;
    typedef typename Sequence::size_type size_type;
    typedef typename Sequence::reference reference;
    typedef typename Sequence::const_reference const_reference;
protected:
    Sequence c;
    Compare comp;
public:
    priority_queue() : c() {}
    explicit priority_queue(const Compare& x) : c(),comp(x) {}

    priority_queue(const value_type* first, const value_type* last, const Compare& x) : c(first, last), comp(x) {
        make_heap(c.begin(), c.end(), comp);
    }
    priority_queue(const value_type* first, const value_type* last) : c(first, last) {
        make_heap(c.begin(), c.end(), comp);
    }

    //判断优先队列是否为空
    bool empty() const {return c.empty();}
    size_type size() const {return c.size();}
    const_reference top() const {return c.front();}
    void push(const value_type& x) {
        try {
            c.push_back(x);
            push_heap(c.begin(), c.end(), comp);
        }
        catch(...) {
            c.clear();
            throw;
        }
    }
    void pop() {
        try {
            pop_heap(c.begin(), c.end(), comp);	// 将最大值放到集合的最后位置
            c.pop_back();							// 
        }
        catch(...) {
            c.clear();
            throw;
        }
    }
};

int main()
{
    // 显式指定模板参数：T=int, Sequence=vector<int>, Compare=less<int>
    priority_queue<int, std::vector<int>, std::less<int>> maxHeap;

    maxHeap.push(30);
    maxHeap.push(10);
    maxHeap.push(50);

    cout << "1.";
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";  // 输出: 50 30 10
        maxHeap.pop();
    }
    cout << endl;

    // // 使用 deque 作为底层容器
    // priority_queue<int, std::deque<int>> pq;

    // pq.push(5);
    // pq.push(2);
    // pq.push(8);

    // while (!pq.empty()) {
    //     std::cout << pq.top() << " ";  // 输出: 8 5 2
    //     pq.pop();
    // }
    return 0;
}